package com.cn.codebrush.动态规划;

/**
 * @Author Boolean
 * @Date 2022/4/28 18:16
 * @Version 1.0
 */
public class No55跳跃游戏 {
    public static void main(String[] args) {
        int[] nums= {2,3,1,1,4};
        int[] nums1= {3,4,1,0,4};
        int[] nums2= {3,3,1,0,4};
        int[] nums3= {3,2,1,0,4};
        int[] nums4= {3,2,1,1,4};
        int[] nums5= {3,2,1,2,4};
        int[] nums6= {0};
        int[] nums7= {0,8};
        int[] nums8= {0,2,3};
        int[] nums9= {1,0,1,0};  //false
        int[] nums10= {2,2,0,2,0,2,0,0,2,0}; //false
        System.out.println(canJump(nums));
        System.out.println(canJump(nums1));
        System.out.println(canJump(nums2));
        System.out.println(canJump(nums3));
        System.out.println(canJump(nums4));
        System.out.println(canJump(nums5));
        System.out.println(canJump(nums9));
        System.out.println(canJump(nums10));
    }

    public static boolean canJump(int[] nums) {
        int n = nums.length;
        if(n==1){
            return true;
        }
        if(nums[0] == 0){
            return false;
        }
        Boolean[] dp = new Boolean[n];
        for(int k=0;k<n;k++){
            dp[k] = false;
        }
        for(int i=0;i<n-1;i++){
            if(nums[i] >= (n-i)){
                return true;
            }
            for(int j=0;j<nums[i];j++){
                dp[i+j+1] = true;
            }
            if(i>0 && dp[i] == false){
                return false;
            }
            if(nums[i] == 0 && dp[i+1] == false){
                return false;
            }
        }
        return dp[n-1];
    }
}
